#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/**
 * 209
 * 二分搜索法
 * [O(nlogn), O(1)]
 */
class Solution{
	public:
		int minSubArrayLen(int s, vector<int>& nums){
			assert(s > 0);
			// sums[i]存放nums[0...i-1]的和
			vector<int> sums(nums.size() + 1, 0);
			for(int i = 1 ; i <= nums.size() ; i ++)
				sums[i] = sums[i-1] + nums[i-1];

			int res = nums.size() + 1;
			for(int l = 0 ; l < (int)nums.size() - 1 ; l ++){

				auto r_bound = lower_bound(sums.begin(), sums.end(), sums[l] + s);
				if(r_bound != sums.end()){
					int r = r_bound - sums.begin();
					res = min(res, r - l);
				}
			}

			if(res == nums.size() + 1)
				return 0;

			return res;
		}

};
